| 翻訳と辞書 |
| Fractional graph isomorphism ： ウィキペディア英語版 |
Fractional graph isomorphism
In graph theory, a fractional isomorphism of graphs whose adjacency matrices are denoted ''A'' and ''B'' is a doubly stochastic matrix ''D'' such that ''DA'' = ''BD''. If the doubly stochastic matrix is a permutation matrix, then it constitutes a graph isomorphism.
Whereas the graph isomorphism problem is not known to be decidable in polynomial time and not known to be NP-complete, the fractional graph isomorphism problem is decidable in polynomial time because it is a special case of the linear programming problem, for which there is an efficient solution.
== Fractional isomorphism is equivalent to coarsest equitable partition ==
Two graphs are also fractionally isomorphic if they have a common coarsest equitable partition. A partition of a graph is a collection of pairwise disjoint sets of vertices whose union is the vertex set of the graph. A partition is equitable if for any pair of vertices ''u'' and ''v'' in the same block of the partition and any block ''B'' of the partition, both ''u'' and ''v'' have the same number of neighbors in ''B''. An equitable partition ''P'' is coarsest if each block in any other equitable partition is a subset of a block in ''P''. Two coarsest equitable partitions ''P'' and ''Q'' are common if there is a bijection ''f'' from the blocks of ''P'' to the blocks of ''Q'' such for any blocks ''B'' and ''C'' in ''P'', the number of neighbors in ''C'' of any vertex in ''B'' equals the number of neighbors in ''f(C)'' of any vertex in ''f(B)''.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Fractional graph isomorphism」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|